package com.skh.binaryTree;

/**
 * @Author: skh
 * @Date: 2020/3/4 10:51
 * @Description: 把二叉搜索树转换为累加树
 */
public class ConvertBST {
    /**
     * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     *
     * 例如：
     *
     * 输入: 二叉搜索树:
     *               5
     *             /   \
     *            2     13
     *
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     */

    //因为二叉搜索树的左子树<根<右子树的性质，按right-root-left的顺序遍历很容易求出累加和
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {

        if (root != null) {
            //从右边开始遍历
            convertBST(root.right);
            sum += root.val; //总和加上自身的值
            root.val = sum; //节点的值为sum
            //开始遍历左边
            convertBST(root.left);
        }

        return root;
    }
}
